The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
A common problem in computing is searching for one or more substrings in a file or a flow of packets in a network. For example, in order to find viruses buried in data files, it is necessary to look for specific sequences of bytes, called “signatures”, which are known in advance and tend to number in the tens of thousands, and typically greater than 100,000. It is CPU-intensive to check each signature against the data file, since 100,000 compare operations are needed for each byte offset in the data file being searched. For example, if the data file is 64 KB in size and the 100,000 digital signatures are all 32 bytes in length then approximately 6.4 billion [(64,000−32+1)*100,000] compare operations must be performed to ensure that the data file is free of the known viruses.
An alternative is to truncate all signatures to a fixed length (e.g. length L) and place each of the known signatures into a hash lookup table. When processing a data file, at every given byte offset, it is only necessary to hash an L consecutive byte sequence in the data file, and then check to see if the sequence matches any of the L bytes of a signature by consulting the hash lookup table.
However, a problem with such an approach is that for each subsequent byte of the data file, the L-byte sliding window is moved forward one byte, and the hash is recomputed. For an M byte data file, it is thus necessary to hash (M−L+1) times. This approach can be expensive since the hash function must re-read (L−1) bytes of the data file, plus the new byte so that the data can be run through the hash function. It is possible that the L−1 bytes of a data file might be cached if L were small enough to fit into a cache. However, for substring searches where L is larger than the available cache, the entire L−1 bytes must be reread as the sliding window is advanced by one byte.
The overhead of computing the hash value of a given sequence of bytes can be greatly decreased if the hash result is independent of the position of the elements in the L bytes being cached. Having each element (usually each element is a byte) act orthogonally on the resultant hash, and shifting the oldest element out of and the newest element into the domain of elements being cached is called a “Rolling Hash”. Rolling Hash was introduced in 1986 as part of the Rabin-Karp substring search algorithm, available at in the document “ibmrd3102P.pdf” in the directory “/journal/rd/312/” of the domain research.ibm.com on the World Wide Web. The Rabin-Karp algorithm proposes that a hash value be the sum of elements, as digits of a base “P” and bounded by the size of the accumulator holding the hash result. For example, if the rolling hash contains the 5 element substring “ABCDE” of the string “ABCDEFG”, and the base, P were 109, then the running hash value would be:HashVal=A*1094+B*1093+C*1092+D*109+E 
In order to slide the window to the right and include “BCDEF”, the operations to perform include 1) removing the weighting of “A”, by subtracting the value (i.e. A*109^4); 2) multiplying the result by 109; and 3) adding in the value of “F”. The result of these three operations is the following new value:HashVal=B*1094+C*1093+D*1092+E*109+F 
If a modulo equal to the precision of the rolling hash accumulator is used, then each re-computation of the hash value as the window slides to the right includes 1) two multiplication operations (e.g. A*1094 must be computed, as well as the previous step 2's multiply by 109); 2) one addition operation (to add in the new value), and 3) one subtract operation (e.g. to subtract out A*1094)
Due to the properties of modulo arithmetic, the fact that the hash accumulator overflows does not compromise the newly computed hash value. (The modulo must be relatively prime to the base, P, which is usually satisfied by using a prime value for P to insure it is relatively prime to the modulus.)
The Rabin-Karp substring search algorithm is useful for multi-substring searches. Various anti-virus software uses the algorithm for searching for virus signatures. However, even though the Rabin-Karp algorithm works well on a general purpose CPU, attempting to implement the algorithm in an application-specific integrated circuit (ASIC) or a field-programmable gate array (FPGA) using a hardware-based algorithm is problematic. The requirement for the two multiplication operations (needing to slide the rolling hash forward one element) places an unwanted burden of the complexity of integer multiplication on an ASIC/FPGA chip.
In another approach (referred to hereinafter as hash-AV) for generating hash values in a substring search context, an exclusive or (XOR) operation and shift are applied on L bytes of data to, respectively, add a new byte and shift out an old byte. XOR and shift operations are readily implemented in hardware. However, such an approach also can be problematic. For example, in a data stream of repeated characters, applying an XOR operation between the same characters effectively cancels out the characters, which makes the resulting hash value useless.